/*
 * File: LocalSearch.c
 *
 * Integrantes:
 * @author	Jormar Arellano		(05-37840)	<jormar.arellano@gmail.com>
 * @author	Sabrina Fernández	(05-38163)	<sabrinamfm@gmail.com>
 */

#include "LocalSearch.h"
#include "graph.h"
#include "arraylist.h"
#include "util.h"

#include <stdio.h>
#include <stdlib.h>

void ls_defaults() {
    ls_iter = 5000;
    ls_verbose = 0;

    ls_acceptance = ls_acceptance_penaltyFunction;
    ls_getNeighbor = getNeighbor_oneExchange;
}

GraphNeighbor *newGraphNeighbor(Graph *graph) {
    GraphNeighbor *ret = (GraphNeighbor *)malloc(sizeof(GraphNeighbor));
    ret->graph = graph;
    ret->changes = arraylist_new(0);

    return ret;
}

GraphNeighbor *createReverseNeighbor(GraphNeighbor *gn) {
    int i;
    Vertex *newv, *v;
    GraphNeighbor *ret = newGraphNeighbor(gn->graph);

    for(i=0; i<gn->changes->length; i++) {
        // Recuperamos el vertice del grafo
        v = gn->changes->data[i];
        v = gn->graph->vertex->data[v->id-1];

        // Creamos una copia de este
        newv = newVertex(v->id);
        newv->color = v->color;
        arraylist_append(ret->changes, newv);
    }

    return ret;
}

void freeGraphNeighbor(GraphNeighbor *gn) {
    int i;

    for(i=0; i<gn->changes->length; i++) {
        freeVertex(gn->changes->data[i]);
    }
    arraylist_free(gn->changes);
    free(gn);
}

Graph *realizeChanges(GraphNeighbor *gn) {
    int i;
    Vertex *v, *vg;
    Graph *g = gn->graph;

    for(i=0; i<gn->changes->length; i++) {
        v = gn->changes->data[i];
        vg = g->vertex->data[v->id-1];

        setColor(g, vg, v->color);
    }

    return g;
}

Graph *newGraphFromChanges(GraphNeighbor *gn) {
    Graph *graph = gn->graph;
    Graph *newg = cloneGraph(graph);

    gn->graph = newg;
    realizeChanges(gn);
    gn->graph = graph;

    return newg;
}

int ls_acceptance_isFactible(GraphNeighbor *gn, int *count) {
    int i, j;
    Vertex *v, *vg, *vn;
    Graph *graph = gn->graph;

    for(i=0; i<gn->changes->length; i++) {
        v = gn->changes->data[i];
        vg = graph->vertex->data[ v->id - 1];

        // Tiene que ser factible
        for(j=0; j<vg->neighbors->length; j++) {
            vn = vg->neighbors->data[j];
            if(vn->color == v->color)
                return 0;
        }
    }

    return 1;
}

int ls_acceptance_bestColor(GraphNeighbor *gn, int *count) {
    int i;
    Vertex *vnew, *vg;
    ArrayList *cvnew, *cvg;
    Graph *graph = gn->graph;
    int resp = 1;

    for(i=0; i<gn->changes->length; i++) {
        vnew = gn->changes->data[i];
        vg = graph->vertex->data[ vnew->id - 1];

        cvnew = graph->Vcolors->data[vnew->color-1];
        cvg = graph->Vcolors->data[vg->color-1];

        resp = resp && (vnew->color != vg->color && cvg->length < 2 && cvnew->length > 0);
    }
    if(resp) {
        *count = 0;

        // VERBOSE
        if(1 <_verbose) printf("    + Puede reducirse a %d colores :D\n", getTotalColor(graph)-1);
    }

    return resp;
}

int ls_acceptance_minConflicts(GraphNeighbor *gn, int *count) {
    int i, j;
    int newTotalConflicts = 0, origTotalConflicts = 0;
    Vertex *vc, *vnew;

    // Calculamos los conflictos del grafo anterior, y del nuevo
    for(i=0; i<gn->changes->length; i++) {
        vnew = gn->changes->data[i];

        for(j=0; j<gn->graph->conflictVertex->length; j++) {
            vc = gn->graph->conflictVertex->data[j];

            if(vc->id == vnew->id) {
                newTotalConflicts += getNumConflict(vnew);
            } else {
                newTotalConflicts += getNumConflict(vc);
            }
            origTotalConflicts += getNumConflict(vc);
        }
    }

    // Nos quedamos con la solucion solo si tiene menos conflictos
    if( origTotalConflicts < newTotalConflicts) {
        return 0;
    } else if (origTotalConflicts > newTotalConflicts) {
        return 1;
    }
    return 1;
}

int ls_acceptance1(GraphNeighbor *gn, int *count) {
    int ret = ls_acceptance_isFactible(gn, count);
    if(ret) ls_acceptance_bestColor(gn, count);

    return ret;
}

int ls_acceptance_penaltyFunction(GraphNeighbor *gn, int *count) {
    int resp;
    long oldPenaltyCost, newPenaltyCost;
    Graph *graph = gn->graph;

    Graph *auxGraph = newGraphFromChanges(gn);
    long newPenaltyCost2 = penaltyCost(auxGraph);

    freeGraph(auxGraph);
    GraphNeighbor *auxNeighbor = createReverseNeighbor(gn);
    realizeChanges(gn);
    newPenaltyCost= penaltyCost(gn->graph);
    realizeChanges(auxNeighbor);

    freeGraphNeighbor(auxNeighbor);

    // DEBUG
    if( newPenaltyCost != newPenaltyCost2 ) {
        printf("  Diferencia entre costos: %ld < %ld\n", newPenaltyCost, newPenaltyCost2);
        // waitStep();
    }

    oldPenaltyCost = penaltyCost(graph);

    // Evaluamos si nos quedamos con la nueva solucion o no
    if(newPenaltyCost < oldPenaltyCost) {
        resp = 1;
        *count = 0;
    } else if(newPenaltyCost == oldPenaltyCost) {
        // Si son iguales, la acepto un 50% de las veces
        resp = rand() % 2;
    } else {
        resp = 0;
    }

    return resp;
}

GraphNeighbor *getNeighbor_oneExchange(Graph *graph) {
    GraphNeighbor *ret = newGraphNeighbor(graph);
    int id;
    int totalColor, newColor;
    Vertex *newv, *v;

    id = (rand()%graph->vertex->length) + 1;
    newv = newVertex(id);
    v =graph->vertex->data[id-1];
    totalColor = getTotalColor(graph);
    do {
        newColor = (rand()%(totalColor+1)) + 1;
    } while(v->color == newColor);

    newv->color = newColor;
    arraylist_append(ret->changes, newv);

    return ret;
}

GraphNeighbor *getNeighbor_minConflicts(Graph *graph) {
    int color, j, index;
    Vertex *vaux, *v, *newv;
    GraphNeighbor *ret;
    int colorTotal = getTotalColor(graph);
    int count;
    int min_count = graph->vertex_number;
    int min_color=0;

    // No hay vertices en conflicto
    if( graph->conflictVertex->length == 0 ) return NULL;

    // Tomamos un vertices conflictivo al azar
    index = (rand() % graph->conflictVertex->length);
    v = graph->conflictVertex->data[index];

    // Buscamos el color que minimiza el numero de conflictos
    for(color=1; color<=colorTotal; color++) {
        count = 0;

        // Contamos los vecinos conflictivos con el nuevo color i+1
        for(j=0; j<v->neighbors->length; j++) {
            vaux = v->neighbors->data[j];
            if(vaux->color == color) count++;
        }

		// Actualizamos el mas pequeno. Si son iguales, escojo al azar.
        if(count<min_count) {
            min_count = count;
            min_color = color;
        } else if (count==min_count && (rand()%2)==0) {
            min_count = count;
            min_color = color;
        }
    }

    // Verificamos que se haya escogido un color, no se cambia el color.
    if(min_color == 0) {
        min_color = v->color;
    }

    // Creamos el cambio y retornamos.
    ret = newGraphNeighbor(graph);
    newv = newVertex(v->id);
    newv->color = min_color;
    arraylist_append(ret->changes, newv);

    return ret;
}

Graph *local_search(Graph *graph) {
    initialSolution(graph);
    return apply_local_search(graph);
}

Graph *apply_local_search(Graph *graph) {
    int i;
    int _aux_i=0;
    GraphNeighbor *ss;

    // Para estadisticas
    long cambios = 0;
    long inicialColors = 0;
    long inicialConflicts = graph->conflictVertex->length;
    long inicialCost = penaltyCost(graph);
    long iTotal = 0;

    inicialColors = getTotalColor(graph);

    for(i=0; i<ls_iter; i++) {
        ss = ls_getNeighbor(graph);

        // En caso de que se haya explorado todo el vecindario.
        if(!ss) break;

        // Evaluo vecino y posiblemente actualizo.
        if(ls_acceptance(ss, &_aux_i)) {
            cambios++;
            realizeChanges(ss);
        }
        freeGraphNeighbor(ss);
        iTotal++;
    }

    // Estadisticas
    if(0 < ls_verbose){
        printf("Reporte de Local Search:\n");
        printf("    >> Colores: %ld ==> %d\n",
                inicialColors, getTotalColor(graph));
        printf("    >> Conflictos: %ld ==> %d\n",
                inicialConflicts,graph->conflictVertex->length);
        printf("    >> Costos: %ld ==> %ld\n",
                inicialCost, penaltyCost(graph));
        printf("    >> Se realizaron %ld cambios a soluciones vecinas\n", cambios);
        printf("    >> Se realizaron %ld iteraciones\n", iTotal);
    }

    return graph;
}
